import java.util.TreeMap;

public class LeetCode211 {

    private class Node{
        public boolean isWord;
        // 指向下一个节点，由于字典树可能有最多26个左右子树，所以这里使用Map
        public TreeMap<Character, Node> next;

        public Node(boolean isWord){
            this.isWord = isWord;
            next = new TreeMap<>();
        }

        public Node(){
            this(false);
        }
    }

    private Node root;

    public LeetCode211() {
        root = new Node();
    }

    public void addWord(String word) {
        Node cur = root;

        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            // 遍历传入的单词中的每一个字母，如果此单词的当前字母不在树上，则加入
            if (cur.next.get(c) == null){
                cur.next.put(c, new Node());
            }
            // 获取下一个字母
            cur = cur.next.get(c);
        }
        // 如果原来的word以前已经在Trie中
        if (!cur.isWord) {
            cur.isWord = true;
        }
    }

    public boolean search(String word) {
        return match(root, word, 0);
    }

    /**
     * 检查给定单词是否与Trie树中的模式匹配。
     *
     * @param node 当前遍历到的Trie树节点。
     * @param word 要匹配的单词或模式。
     * @param index 当前正在比较的字符在单词中的索引。
     * @return 如果单词与模式匹配，则返回true；否则返回false。
     */
    private boolean match(Node node, String word, int index){
        // 如果已经比较到单词的最后一个字符，检查当前节点是否是一个单词的结尾。
        if (index == word.length()){
            return node.isWord;
        }
        char c = word.charAt(index);
        // 如果当前字符不是通配符'.'
        // 如果当前字母不是. 而是一个普通的字母
        if (c != '.'){
            // 如果当前节点没有以c为开头的子节点，说明匹配失败。
            // 如果没有c这个字符
            if (node.next.get(c) == null){
                return false;
            }
            // 继续在下一个节点上匹配下一个字符。
            return match(node.next.get(c), word, index + 1);
        }else {
            // 如果当前字符是通配符'.', 则尝试匹配任何字符。
            for (char nextChar : node.next.keySet()) {
                // 如果通过当前节点的任意一个子节点能够匹配成功，则整个匹配成功。
                if (match(node.next.get(nextChar), word,index +1)){
                    return true;
                }
            }
            // 如果所有可能的字符都无法匹配，则匹配失败。
            return false;
        }
    }



/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */
}
